#include <iostream>
#include <queue>
#include <algorithm>

using namespace std;

const int MAXN = 1000, MAXM = 1000000, INF = 10001000;
int n = 9, m = 28; // |V|=n, |E|=m
int u[MAXM] = {0,0,1 ,1,2,2,8,8,3,3,4,5 ,5,6 ,1,2,2 ,3,8,4,3,4,5,6,6,6 ,7,7 };
int v[MAXM] = {1,2,2 ,3,8,4,3,4,5,6,6,6 ,7,7 ,0,0,1 ,1,2,2,8,8,3,3,4,5 ,5,6 };
int w[MAXM] = {4,8,11,8,7,1,2,6,7,4,2,14,9,10,4,8,11,8,7,1,2,6,7,4,2,14,9,10};
int d[MAXN];
bool inq[MAXN];
int first[MAXN], next[MAXN];

void read_graph() {
    for (int i = 0; i < n; ++i) first[i] = -1;
    for (int e = 0; e < m; ++e) {
        next[e] = first[u[e]];
        first[u[e]] = e;
    }
}

void Bellman_Ford_FIFO() {
    queue<int> q;
    for (int i = 0; i < n; ++i) d[i] = (i == 0 ? 0 : INF);
    q.push(0);
    while (!q.empty()) {
        int x = q.front(); q.pop();
        inq[x] = false;
        for (int e = first[x]; e != -1; e = next[e])
            if (d[v[e]] > d[x] + w[e]) {
                d[v[e]] = d[x] + w[e];
                if (!inq[v[e]]) {
                    inq[v[e]] = true;
                    q.push(v[e]);
                }
            }
    }
}

int main() {
    read_graph();
    Bellman_Ford_FIFO();
    for (int i = 0; i < n; ++i) cout << d[i] << ' ';
    cout << endl;
}

